package com.ken.algorithms.stack;

import java.util.Stack;

/**
 * <ul>
 * <li>Title: MainCD13</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/18 0018 上午 8:43
 */
public class MainCD13 {


    /**
     * 功能描述: 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，
     * 只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
     * @param args
     * @return: void
     * @author: 程序员ken
     * @date: 2021/5/18 0018 上午 8:49
    */
    public static void main(String[] args) {
        Stack<Integer> stack1 = new Stack<Integer>();
        int[] arr ={136,12,93,0,82,1};
        for (int i = 0; i < arr.length; i ++) {
            // 栈顶到栈底的各个元素
            stack1.push(arr[i]);
        }
        sortStackByStack(stack1);
        while (!stack1.isEmpty()) {
            System.out.print(stack1.pop() + " ");
        }
    }

    private static void sortStackByStack(Stack<Integer> stack1) {
        Stack<Integer> help = new Stack<Integer>();
        //因为这个 必须要在两个容器中置换  只能换位置 原栈 必须采取出栈的策略 最终辅助‘栈’才是有序的 把他赋值给他
       /* while (!stack1.isEmpty()){
            int cur = stack1.pop();
            // 1. 辅助栈为空，直接入辅助栈
            if(help.isEmpty()){
                help.push(cur);
            }
            // 2. 当前元素 <= 辅助栈的栈顶元素，直接入辅助栈
            else if(cur <= help.peek()){
                help.push(cur);
            }else{
                // 直到当前元素 <= 辅助栈的栈顶元素，就停止辅助栈的出栈操作
                while (!help.isEmpty() && help.peek()<cur){
                    stack1.push(help.pop());
                }
                help.push(cur);
            }
        }*/
       // 变形
        while (!stack1.isEmpty()){
            int cur = stack1.pop();
            // 直到当前元素 <= 辅助栈的栈顶元素，就停止辅助栈的出栈操作
            while (!help.isEmpty() && help.peek()<cur){
                 stack1.push(help.pop());
            }
            help.push(cur);
        }
        // 将辅助栈元素导入原栈
        while (!help.isEmpty()) {
            stack1.push(help.pop());
        }
    }


}
